//N皇后 力扣51
//对棋盘的回溯算法，树层遍历的是每一行上的每一个位置，树枝遍历的是不同行
//棋盘的条件检查（横向，纵向，斜向）
class Solution {
public:
	vector<vector<string>> ans;
	bool isvalid(vector<string> chessboard,int col,int row,int n)
	{
		//检查列
		for(int i = 0; i < row; i++)
			if(chessboard[i][col] == 'Q') return false;
		//检查45度
		for(int i = row-1, j = col+1; i>=0 && j<n; i--,j++)
			if(chessboard[i][j] == 'Q') return false;
		//检查135度
		for(int i = row-1, j = col-1; i>=0 && j>=0;i--,j--)
			if(chessboard[i][j] == 'Q') return false;
		return true;
	}
	void backtracking(vector<string>& chessboard,int n,int row)
	{
		if(row == n)
		{
			ans.push_back(chessboard);
			return ;
		}
		for(int col = 0; col < n; col++)
		{
			if(!isvalid(chessboard,col,row,n)) continue;
			chessboard[row][col] = 'Q';
			backtracking(chessboard,n,row+1);
			chessboard[row][col] = '.';
		}
	}
	vector<vector<string>> solveNQueens(int n) {
		vector<string> chessboard(n,string(n,'.'));
		backtracking(chessboard,n,0);
		return ans;
	}
};
